package listbyorder.access001_100.test28;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/29 18:12
 */
public class Solution2 {

    // 方法二： KMP算法
    public int strStr(String haystack, String needle) {
        // 边界条件
        if (haystack == null || needle == null || haystack.length() < needle.length()) return -1;
        if (needle.length() == 0) return 0;
        // 将两个字符串转化为字符数组
        char[] chs = haystack.toCharArray();
        char[] chm = needle.toCharArray();
        // 计算m字符串的next数组
        int[] next = getNextArr(chm);
        int si = 0;   // chs的指针
        int sm = 0;   // chm的指针
        while (si < chs.length && sm < chm.length) {
            if (chs[si] == chm[sm]) {
                si++;
                sm++;
            } else if (next[sm] == -1) {
                si++;
            } else {
                sm = next[sm];
            }
        }
        return sm == chm.length ? si - sm : -1;
    }

    // 指定字符数组，生成next数组
    private int[] getNextArr(char[] chars) {
        if (chars.length == 1) return new int[]{-1};
        int[] next = new int[chars.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        int pos = 2;
        while (pos < chars.length) {
            if (chars[pos - 1] == chars[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }
}
